백준 3273번 - 두수의 합

문제링크

풀이

전형적인 2 pointer 문제라고 할 수 있다.
2 포인터의 조건인 list안에서 움직이는 2가지 포인터로 문제를 쉽게 풀 수 있다.

1. 양쪽 끝에서 포인터를 초기화하고
2. 합이 작으면 왼쪽 포인터를 크면 오른쪽 포인터를 옮긴다.
3. 합이 x에 도달하면 count

포인터 구현 코드

rl.on("close", () => {
  const n = input.shift()[0];
  const arr = input.shift();
  const x = input.shift()[0];
  arr.sort((a, b) => a - b);
  let start = 0;
  let end = n - 1;
  let count = 0;
  while (start < end) {
    const sum = arr[start] + arr[end];
    if (sum == x) {
      count++;
      start++;
      end--;
    } else if (sum < x) {
      start++;
    } else {
      end--;
    }
  }
  console.log(count);
});

이진 탐색 코드

이진 탐색으로 문제를 풀 수도 있다.

rl.on("close", () => {
  const n = input[0][0];
  const a = input[1];
  const x = input[2][0];
  a.sort((a, b) => a - b);
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (a[i] >= x) {
      break;
    }
    if (binarySearch(a, i + 1, n - 1, x - a[i])) {
      count++;
    }
  }
  function binarySearch(arr, start, end, v) {
    while (start <= end) {
      let mid = parseInt((start + end) / 2);
      if (arr[mid] == v) {
        return true;
      } else if (arr[mid] > v) {
        end = mid - 1;
      } else {
        start = mid + 1;
      }
    }
    return false;
  }
  console.log(count);
  n;
});